class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        // 状态表示
        int[] len = new int[n]; // 以 i 位置为结尾的子序列的最大长度
        int[] count = new int[n]; // 以 i 位置为结尾的最大长度子序列的个数
        // 初始化
        for(int i = 0; i < n; i++){
            len[i] = 1;
            count[i] = 1;
        }
        // 状态转移
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    if(len[i] < len[j] + 1){
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }else if(len[i] == len[j] + 1){
                        count[i] += count[j];
                    }
                }
            }
        }
        // 返回值
        int maxLen = 0;
        int ret = 0;
        for(int i = 0; i < n; i++){
            if(maxLen < len[i]){
                maxLen = len[i];
                ret = count[i];
            }else if(maxLen == len[i]){
                ret += count[i];
            }
        }
        return ret;
    }
}